Tablut Challenge

Slides

Intro

Hello, I'm Wei Jinqi, the only member of my team Shan. in Chinese it means mountain. It's just for fun that finishing projects is like climbing mountains. And this is one of the mountains. Today I'm going to share my approach to the challenge tablut. As the first team to pre here, I'm glad to set a base line to share the experiences with everyone.

Structure

First, here we can see the structure of my client to evaluate new move. The key algorithm is minimax with Alpha-Beta pruning.
But I'm not going to talking about the minimax itself, as we have already learnt about it. We all know that, there are two key points in this kind of search algorithm: 1. how to evaluate the situation 2. how fast to search

strategy

$s c o r e = f_{s n} + f_{d p} + f_{k s} + f_{p}$
- Solider Number.
  $f_{s n} = c_{w} * N_{w_s o l i d e r} + c_{b} * N_{b_s o l i d e r}$ , $c_{w} = 160 / 8, c_{b} = - 160 / 16$ .
  For black, reverse the sign.
- Direct Path (to escape). For white,
  
  c_{escape}, & n_path = 1 \
  
  \frac{BIG_NUM}{2}, & n_path \geq 1
  
  \end{cases},
  
  {c}_{escape} = 20
  
  \frac{BIG_NUM}{4}, & n_path = 1 \
  
  \frac{BIG_NUM}{2}, & n_path \geq 1
  
  \end
  - If the king is in the castle, for each adjacent black soldier, -20.
  - If the king is adjacent to the castle, for each adjacent black soldier or camp, -30.
  - If the king is not adjacent to the castle, for each adjacent black soldier or camp, -50.
  - If the king is in these four areas, the FLAT_AREA, the king safety score adds depends on the number of black soldiers in the same area with table below:
- Position Score $f_{p}$ : precomputed positional score table for both roles.
  - $f_{p} = \sum_{i, j = 0}^{i, j = 9} w e i g h t_{i j} * o n_{i j}$
- coefficient
Early Termination
- makes Alpha-Beta pruning much more efficient, check captures first and eval a BIG_NUMBER to Quick fall
- For later win solution, eval a number less than BIG_NUMBER but still big, like BIG_NUMBER/2
Multiprocess Searching
- send tasks to 4 process to use 4 cores of CPU (can be the number of cores of the machine)
- handle timeout easily. But one problem is that sub-tree state is lost if break from timeout with recursion search. To handle timeout more efficiently could implement search functions with loop.
- default depth is 3.
Docker based development env
pure-python implementation for server and client. better for learning based algorithm.

Experience

A deeper search isn't always better if the evaluation function is weak. Deeper cost much more time, and 4/5 layers search worse than good evaluation with 3 layers search
Too much engineering work can be done.

Conclusion

That's all
If I had more time, I would implement Monte Carlo Tree Search (MCTS), which is used in AlphaZero to defeat world-champions by Google Deepmind.

Q&A

If there's any question, ask for me

Info:

Github: Bardreamaster/pytablut: Tablut implemented in Python
Docs: pytablut documentation

Slides

Result

AlphaZero